home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
PROGRAM
/
NTUMIN10.ARJ
/
CAMPF.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-03-09
|
15KB
|
443 lines
/****************************************************************************
*
* Program name : CAMPF.C
*
* This is the actual minimization algorithm. Variation from the actual
* CAMP algorithm is as follows:
* 1. Minterms with adjacency 0 or 1 is minimised first
* 2. Select next minterm with lowest adjacency wrt b-array
* 3. If more than 1 such minterms, select one with the lowest
* adjacency wrt to a-array
* 4. To shrink the CPT, select an adjacent term, mi that has the
* largest wi AND is already covered
* 5. If more than one such adjacent terms are covered, select one
* with the lowest adjacency wrt to b-array
* 6. If non of the adjacent term is covered, select one with the
* lowest adjacency wrt b-array from the uncovered adj term
* at step 4.
*
* --------------------------------------------------------------------------
* Copyright (c) 1992. All Rights Reserved. Nanyang Technological
* University.
*
* You are free to use, copy and distribute this software and its
* documentation providing that:
*
* NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
*
* IT IS NOT MODIFIED IN ANY WAY.
*
* THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
*
* This program is provided "AS IS" without any warranty, expressed or
* implied, including but not limited to fitness for any particular
* purpose.
*
* If you find NTUMIN fast, easy, and useful, a note or comment would be
* appreciated. Please send to:
*
* Boon-Tiong Tan or Othman Bin Ahmad
* School of EEE
* Nanyang Technological University
* Nanyang Avenue
* Singapore 2263
* Republic of Singapore
*
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mask8 255
unsigned char *campf(a, b) /* pointer to a & b array passed */
unsigned char *a, *b;
{
unsigned short pterm, ma, mb, *pm, *pm1, *point, pos, pos1;
unsigned long m, k, topow();
register long i, wo, wi;
register char j;
char test;
unsigned char *c, *d, *e, *s, *temp, count, adj0, adji;
unsigned char n, adj, adjacency(), nspm, cover;
unsigned char *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
n = *a; /* no. of variables */
nspm = *(a+3); /* no. of bytes/minterm */
ma = *(a+2)<<8 | *(a+1); /* no. of minterms in a-array */
temp = (unsigned char *) malloc(nspm+1); /* temporary storage */
if (temp == 0)
{
printf("Out of memory -- CAMPF, *temp\n");
printf("Program terminated - 1\n");
exit(0);
}
s = (unsigned char *) malloc(4); /* header of s-array */
if (s == 0)
{
printf("Out of memory -- CAMPF, *s\n");
printf("Program terminated - 2\n");
exit(0);
}
pterm = 0; /* no. of product term */
/***
*** MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
***/
for (i=0; i<mb; i++) /* for adj = 0 or 1 */
{
*b = n; /* assign back to n */
memcpy(temp, (b+4+nspm*i), nspm); /* pick a minterm from b-array */
c = adjacent(temp, a, 1); /* obtain the adjacent terms */
adj = *(c+1); /* adjacency of minterm */
if (adj <= 1) /* adjacency 0 or 1 */
{
d = cpt(c); /* generate CPT */
s = (unsigned char *) realloc(s,4+n*(pterm+1)); /* more space */
if (s == 0)
{
printf("Out of memory -- CAMPF, *s\n");
printf("Program terminated - 3\n");
exit(0);
}
memcpy ((s+4+n*pterm),d,n); /* add CPT to soln array */
pterm++; /* product term count */
b = reduce(c,b,i); /* remove minterms covered from b-array */
i = (char) *b; /* index pointer of b-array */
mb = *(b+2)<<8 | *(b+1); /* value of mb altered in b-array */
free(d); /* free pointer */
}
free(c); /* free pointer */
}
/***
*** MINIMIZE MINTERMS WITH ADJACENCY GREATER THAN 1
***/
while (mb > 0)
{
adj0 = 255; /* max for 8-bit */
*b = n; /* assign back to n */
/***
*** OBTAIN AN ARRAY, PM OF POSITION OF ADJACENT TERMS WITH THE LOWEST
*** ADJACENCY WRT B-ARRAY
***/
for (i=0; i<mb; i++)
{
memcpy(temp, (b+4+nspm*i), nspm); /* pick a minterm */
adji = adjacency(temp, b); /* adj wrt b-array */
if (adji<adj0) /* look for lowest adj */
{
if (adj0!=255) /* not the 1st term */
free(pm);
adj0 = adji; /* update lowest adj */
count = 1; /* set count to 1 */
pm = (unsigned short *) malloc(2); /* space for pos */
if (pm == 0)
{
printf("Out of memory -- CAMPF, *pm\n");
printf("Program terminated - 4\n");
exit(0);
}
*pm = i; /* 1st pos of minterm */
}
else if (adji==adj0) /* adjacency as low */
{
count++; /* no. of elements in pm-array */
pm = (unsigned short*) realloc(pm, 2*count); /* more space */
if (pm == 0)
{
printf("Out of memory -- CAMPF, *pm\n");
printf("Program terminated - 5\n");
exit(0);
}
*(pm+count-1) = i; /* elements in pm-array */
}
}
if (count==1) /* if only 1 element in pm-array */
pos = *pm;
else
{
/***
*** FORM PM-ARRAY, SELECT THE 1ST ADJACENT TERM THAT HAS THE
*** LOWEST ADJACENCY WRT A-ARRAY
***/
adj0 = 255; /* max for 8-bit */
for (i=0; i<count; i++) /* do for all in pm-array */
{
pos1 = *(pm+i); /* pos of minterm */
memcpy(temp, (b+4+nspm*pos1), nspm);
adji = adjacency(temp, a); /* adj wrt a-array */
if (adji<adj0) /* new lowest found */
{
adj0 = adji; /* update lowest */
pos = *(pm+i); /* position of required minterm */
}
}
}
free(pm);
memcpy(temp, (b+4+nspm*pos), nspm); /* pick the required minterm */
/***
*** GENERATE SSM AND TEST FOR COVERAGE BY FUNCTION
***/
c = adjacent(temp, a, 255); /* obtain adjacent terms */
adj = *(c+1); /* adjacency of minterms */
d = cpt(c); /* generate CPT */
e = ssm(d); /* generate SSM */
m = topow(*(e+1)); /* no. of SSM terms */
for (j=0; j<m; j++) /* check for SSM coverage */
{
memcpy (temp, (e+4+nspm*j), nspm);
test = exist (temp, a, ma);
if (test == -1) /* SSM term not in a-array */
break;
}
/***
*** ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
***/
if (test == 0) /* all SSM's covered by fn */
{
if (m > 65536) /* too many SSM terms */
{
printf("Product Term Too Huge \n");
printf("Program terminated \n");
exit(0);
}
*(e+1) = (m-1) & mask8; /* no. of SSM terms minus 1 */
*(e+2) = (m-1)>>8 & mask8;
b = reduce(e,b,i); /* remove minterms covered from b-array */
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
if (s == 0)
{
printf("Out of memory -- CAMPF, *s\n");
printf("Program terminated - 6\n");
exit(0);
}
memcpy((s+4+n*pterm),d,n); /* add CPT to soln array */
pterm++; /* no. of product terms */
free(d); /* free pointers */
free(e);
}
else
{
/***
*** SSM NOT COVERED BY THE FUNCTION
***/
free(d); /* free pointer */
cover =0; /* coverage status */
while (!cover) /* do until shrinked SSM is covered */
{
/***
*** OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS, MI WITH THE LARGEST WI
***/
wo = -1; /* initial value */
for (j=0; j<adj; j++) /* do for all adjacent terms */
{
memcpy(temp,(c+4+nspm*(j+1)),nspm); /* pick adjacent term */
wi = adj_of_mi(temp,e,a); /* obtain wi */
if (wi>wo)
{
if (wo != -1) /* not the first */
free(pm);
wo = wi; /* new lowest value */
count = 1; /* reset count to 1 */
pm = (unsigned short *) malloc(2); /* space for pm */
if (pm==0)
{
printf("Out of memory -- CAMPF, *pm\n");
printf("Program terminated - 7\n");
exit(0);
}
*pm = j; /* first element */
}
else if (wi==wo) /* wi as large */
{
count++; /* no. of element in pm-array */
pm = (unsigned short *) realloc (pm, 2*count); /* more space */
if (pm==0)
{
printf("Out of memory -- CAMPF, *pm\n");
printf("Program terminated - 8\n");
exit(0);
}
*(pm+count-1) = j; /* elements of pm-array */
}
}
free(e); /* free pointer */
/***
*** DETERMINE FROM PM-ARRAY, AN ARRAY, PM1 OF POSITION OF ADJACENT TERMS
*** THAT HAVE ALREADY BEEN COVERED
***/
pm1 = (unsigned short *) malloc(2); /* space for pm1 */
if (pm1==0)
{
printf("Out of memory -- CAMPF, *pm1\n");
printf("Program terminated - 9\n");
exit(0);
}
k = 0;
for (j=0; j<count; j++) /* do for all element in pm-array */
{
memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm); /* pick adj term */
test = exist(temp,b,mb);
if (test == -1) /* already covered */
{
memcpy((pm1+k++), (pm+j), 2); /* transfer pos to pm1 */
pm1 = (unsigned short *) realloc(pm1, 2*(k+1)); /* more space */
if (pm1==0)
{
printf("Out of memory -- CAMPF, *pm1\n");
printf("Program terminated - 10\n");
exit(0);
}
}
}
/***
*** SELECT FROM PM1-ARRAY (IF EMPTY, SELECT FROM PM-ARRAY),
*** THE 1ST ADJACENT TERM, MI WITH THE LOWEST ADJACENCY WRT B-ARRAY
***/
if (k == 0) /* non covered, pm1 empty */
{
k = count; /* look for lowest adj term in pm-array */
point = pm;
}
else
point = pm1; /* look for lowest adj term in pm1-array */
adj0 = 255; /* max of 8-bit */
for (j=0; j<k; j++) /* do for all in pm1/pm-array */
{
memcpy(temp,(c+4+nspm*(1+*(point+j))),nspm); /* pick an adj term */
adji = adjacency(temp,b); /* obtain adjacency */
if (adji<=adj0) /* new lowest found */
{
adj0 = adji; /* update lowest */
pos = *(point+j); /* position of lowest adj term */
}
}
adj--; /* no. of adj terms in c-array */
*(c+1) = adj; /* adjacency after shrinking CPT */
free(pm); /* free pointer */
free(pm1);
/***
*** SHRINK CPT (REMOVE 1 ADJACENT TERM FROM C-ARRAY), GENERATE NEW CPT, SSM
*** AND TEST FOR COVERAGE BY FUNCTION
***/
memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos)); /* shrink CPT */
c = (unsigned char*) realloc(c, 4+nspm*(1+adj)); /* reduce space */
if (c==0)
{
printf("Out of memory -- CAMPF, *c\n");
printf("Program terminated - 11\n");
exit(0);
}
d = cpt(c); /* generate CPT */
e = ssm(d); /* generate SSM */
m = topow(*(e+1)); /* no. of SSM terms */
for (i=0; i<m; i++) /* check SSM coverage by function */
{
memcpy(temp, (e+4+nspm*i), nspm); /* pick SSM term */
test = exist(temp,a,ma);
if (test == -1) /* SSM term not covered */
break;
}
/***
*** SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY
*** AND SELECT SHRINKED CPT AS PRODUCT TERM
***/
if (test==0) /* SSM covered */
{
if (m > 65536) /* too many SSM terms */
{
printf("Product Term Too Huge \n");
printf("Program terminated \n");
exit(0);
}
*(e+1) = (m-1) & mask8; /* no. of SSM terms minus 1 */
*(e+2) = (m-1)>>8 & mask8;
b = reduce(e, b, i); /* remove minterms covered from b-array */
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
if (s==0)
{
printf("Out of memory -- CAMPF, *s\n");
printf("Program terminated - 12\n");
exit(0);
}
memcpy ((s+4+n*pterm), d, n); /* add shrinked CPT to soln array */
pterm++; /* no. of product terms */
cover = 1; /* coverage status */
free(e); /* free pointer */
}
free (d); /* free pointer */
}
}
free(c); /* free pointer */
}
*s = n; /* no. of variables */
*(s+1) = pterm & mask8; /* no. of product terms in 2 bytes */
*(s+2) = pterm>>8 & mask8;
free(temp); /* free pointer */
free(a);
free(b);
return(s); /* return solution array */
}
